import os, sys

# 把包的父目录添加到系统搜索路径
BASE_DIR=os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
sys.path.append(BASE_DIR)

from base_data_structures.stack import Stack
from base_data_structures.tree import BinaryTree 

# 构造解析树
def buildParseTree(fpexp):
    fplist = fpexp.split()

    # 利用栈结构， 下沉时压栈， 上升时出栈
    # 提供一个由子节点找到父节点的方法
    pStack = Stack()

    eTree = BinaryTree('')
    pStack.push(eTree)

    currentTree = eTree

    # 解析表达式， 构建解析树的规则：
    #     1 如果当前单词时"(", 为当前节点添加一个左子节点， 当前节点下降为这个新节点。
    #     2 如果当前但是时操作符: 将当前节点的值设为此符号， 为当前节点添加要给右子节点，
    #       当前节点下降为这个新节点。
    #     3 如果当前单词时操作数：将当前节点的值设为此数， 当前节点上升到父节点。
    #     4 当前单词是")", 则当前节点上升到父节点。
    for i in fplist:
        if i=='(':
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree=currentTree.getLeftChild()
        elif i not in ['+', '-', '*', '/', ')']:
            currentTree.setRootVal(int(i))
            parent = pStack.pop()
            currentTree=parent
        elif i in ['+', '-', '*', '/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree=currentTree.getRightChild()
        elif i == ')':
            currentTree=pStack.pop()
        else:
            raise ValueError
    return eTree


# 利用解析树进行计算
#   利用了递归算法
import operator

def evaluate(parseTree):
    opers = {'+':operator.add, '-':operator.sub,
        '*': operator.mul, '/': operator.truediv}
    leftC = parseTree.getLeftChild()
    rightC = parseTree.getRightChild()
    
    if leftC and rightC:
        fn =opers[parseTree.getRootVal()]
        # 缩小规模， 调用自己
        return fn(evaluate(leftC),evaluate(rightC))
    else:
        # 基本结束条件
        return parseTree.getRootVal()

# 采用后续遍历重写表达式求值
def postordereval(tree):
    opers = {'+':operator.add, '-':operator.sub,
        '*': operator.mul, '/': operator.truediv}
    res1=None
    res2 = None
    if tree:
        res1 = postordereval(tree.getLeftChild())
        res2 = postordereval(tree.getRightChild())
        if res1 and res2:
            return opers[tree.getRootVal()](res1, res2)
        else:
            return tree.getRootVal()

parseTree=buildParseTree("( ( 3 +  4 ) * 5 )")
print(evaluate(parseTree))
print(postordereval(parseTree))


